In computer science, a ticket lock is a locking algorithm that is a type of spinlock which uses "tickets" to control which thread of execution is allowed to enter a critical section.
Contents |
A ticket lock works as follows; there are two integer values which begin at 0. The first value is the queue ticket, the second is the dequeue ticket.
When a thread arrives, it atomically obtains and then increments the queue ticket. It then atomically compares its ticket with the dequeue ticket. If they are the same, the thread is permitted to enter the critical section. If they are not the same, then another thread must already be in the critical section and this thread must busy-wait or yield. When a thread leaves the critical section controlled by the lock, it atomically increments the dequeue ticket. This permits the next waiting thread to enter the critical section.
The advantage of a ticket lock over other spinlock algorithms is that it is fair. The waiting threads are processed in a first-in first-out basis as the dequeue ticket integer increases, thus preventing starvation. It also prevents the thundering herd problem occurring since only one thread at a time tries to enter the critical section. The Linux kernel implementation can have lower latency than the simpler test-and-set or exchange based spinlock algorithms on modern machines.
This algorithm was introduced into the Linux kernel in 2008 due to its advantages,[1] but was omitted in paravirtualized environments where it had disadvantages.[2] As of July 2010[update], work is in progress to enable the use of ticket locks in paravirtualization.[3][4]